package 分类.一维动规;

public class 爬楼梯 {// 备忘录
    int[] memo;

    public int climbStairs(int n) {
        memo=new int[n+1];
        return dp(n);
    }

    int dp(int n){
        if(n<2){
            memo[n]=n;
            return n;
        }
        if(memo[n]>0){
            return memo[n];
        }
        memo[n]=dp(n-1)+dp(n-2);
        return memo[n];
    }
}
